home *** CD-ROM | disk | FTP | other *** search
/ Cream of the Crop 21 / Cream of the Crop 21 (Terry Blount) (October 1996).iso / program / srcbkvt.zip / RR796.ASC < prev   
Text File  |  1996-07-08  |  16KB  |  387 lines
  1. _Rambling In Real Time_
  2. by Michael Abrash
  3.  
  4. Listing One
  5.  
  6. // Part of Win32 program to demonstrate z-sorted spans. Whitespace removed for
  7. // space. Full source code available at ftp.idsoftware.com/mikeab/ddjzsort.zip.
  8. #define MAX_SPANS           10000
  9. #define MAX_SURFS           1000
  10. #define MAX_EDGES           5000
  11. typedef struct surf_s {
  12.     struct surf_s   *pnext, *pprev;
  13.     int             color, visxstart, state;
  14.     double          zinv00, zinvstepx, zinvstepy;
  15. } surf_t;
  16. typedef struct edge_s {
  17.     int             x, xstep, leading;
  18.     surf_t          *psurf;
  19.     struct edge_s   *pnext, *pprev, *pnextremove;
  20. } edge_t;
  21. // Span, edge, and surface lists
  22. span_t  spans[MAX_SPANS];
  23. edge_t  edges[MAX_EDGES];
  24. surf_t  surfs[MAX_SURFS];
  25. // Bucket list of new edges to add on each scan line
  26. edge_t  newedges[MAX_SCREEN_HEIGHT];
  27. // Bucket list of edges to remove on each scan line
  28. edge_t  *removeedges[MAX_SCREEN_HEIGHT];
  29. // Head and tail for the active edge list
  30. edge_t  edgehead, edgetail;
  31. // Edge used as sentinel of new edge lists
  32. edge_t  maxedge = {0x7FFFFFFF};
  33. // Head/tail/sentinel/background surface of active surface stack
  34. surf_t  surfstack;
  35. // pointers to next available surface and edge
  36. surf_t  *pavailsurf;
  37. edge_t  *pavailedge;
  38.  
  39. // Returns true if polygon faces the viewpoint, assuming a clockwise
  40. // winding of vertices as seen from the front.
  41. int PolyFacesViewer(polygon_t *ppoly, plane_t *pplane)
  42. {
  43.     int     i;
  44.     point_t viewvec;
  45.  
  46.     for (i=0 ; i<3 ; i++)
  47.         viewvec.v[i] = ppoly->verts[0].v[i] - currentpos.v[i];
  48.     // Use an epsilon here so we don't get polygons tilted so
  49.     // sharply that the gradients are unusable or invalid
  50.     if (DotProduct (&viewvec, &pplane->normal) < -0.01)
  51.         return 1;
  52.     return 0;
  53. }
  54. // Add the polygon's edges to the global edge table.
  55. void AddPolygonEdges (plane_t *plane, polygon2D_t *screenpoly)
  56. {
  57.     double  distinv, deltax, deltay, slope;
  58.     int     i, nextvert, numverts, temp, topy, bottomy, height;
  59.     edge_t  *pedge;
  60.  
  61.     numverts = screenpoly->numverts;
  62.     // Clamp the polygon's vertices just in case some very near
  63.     // points have wandered out of range due to floating-point imprecision
  64.     for (i=0 ; i<numverts ; i++) {
  65.         if (screenpoly->verts[i].x < -0.5)
  66.             screenpoly->verts[i].x = -0.5;
  67.         if (screenpoly->verts[i].x > ((double)DIBWidth - 0.5))
  68.             screenpoly->verts[i].x = (double)DIBWidth - 0.5;
  69.         if (screenpoly->verts[i].y < -0.5)
  70.             screenpoly->verts[i].y = -0.5;
  71.         if (screenpoly->verts[i].y > ((double)DIBHeight - 0.5))
  72.             screenpoly->verts[i].y = (double)DIBHeight - 0.5;
  73.     }
  74.     // Add each edge in turn
  75.     for (i=0 ; i<numverts ; i++) {
  76.         nextvert = i + 1;
  77.         if (nextvert >= numverts)
  78.             nextvert = 0;
  79.         topy = (int)ceil(screenpoly->verts[i].y);
  80.         bottomy = (int)ceil(screenpoly->verts[nextvert].y);
  81.         height = bottomy - topy;
  82.         if (height == 0)
  83.             continue;       // doesn't cross any scan lines
  84.         if (height < 0) {
  85.             // Leading edge
  86.             temp = topy;
  87.             topy = bottomy;
  88.             bottomy = temp;
  89.             pavailedge->leading = 1;
  90.             deltax = screenpoly->verts[i].x -
  91.                      screenpoly->verts[nextvert].x;
  92.             deltay = screenpoly->verts[i].y -
  93.                      screenpoly->verts[nextvert].y;
  94.             slope = deltax / deltay;
  95.             // Edge coordinates are in 16.16 fixed point
  96.             pavailedge->xstep = (int)(slope * (float)0x10000);
  97.             pavailedge->x = (int)((screenpoly->verts[nextvert].x +
  98.                 ((float)topy - screenpoly->verts[nextvert].y) *
  99.                 slope) * (float)0x10000);
  100.         } else {
  101.             // Trailing edge
  102.             pavailedge->leading = 0;
  103.             deltax = screenpoly->verts[nextvert].x -
  104.                      screenpoly->verts[i].x;
  105.             deltay = screenpoly->verts[nextvert].y -
  106.                      screenpoly->verts[i].y;
  107.             slope = deltax / deltay;
  108.             // Edge coordinates are in 16.16 fixed point
  109.             pavailedge->xstep = (int)(slope * (float)0x10000);
  110.             pavailedge->x = (int)((screenpoly->verts[i].x +
  111.                 ((float)topy - screenpoly->verts[i].y) * slope) *
  112.                 (float)0x10000);
  113.         }
  114.         // Put the edge on the list to be added on top scan
  115.         pedge = &newedges[topy];
  116.         while (pedge->pnext->x < pavailedge->x)
  117.             pedge = pedge->pnext;
  118.         pavailedge->pnext = pedge->pnext;
  119.         pedge->pnext = pavailedge;
  120.         // Put the edge on the list to be removed after final scan
  121.         pavailedge->pnextremove = removeedges[bottomy - 1];
  122.         removeedges[bottomy - 1] = pavailedge;
  123.         // Associate the edge with the surface we'll create for this polygon
  124.         pavailedge->psurf = pavailsurf;
  125.         // Make sure we don't overflow the edge array
  126.         if (pavailedge < &edges[MAX_EDGES])
  127.             pavailedge++;
  128.     }
  129.     // Create the surface, so we'll know how to sort and draw from the edges
  130.     pavailsurf->state = 0;
  131.     pavailsurf->color = currentcolor;
  132.     // Set up the 1/z gradients from the polygon, calculating the base value at
  133.     // screen coordinate 0,0 so we can use screen coordinates directly when 
  134.     // calculating 1/z from the gradients
  135.     distinv = 1.0 / plane->distance;
  136.     pavailsurf->zinvstepx = plane->normal.v[0] * distinv *
  137.             maxscreenscaleinv * (fieldofview / 2.0);
  138.     pavailsurf->zinvstepy = -plane->normal.v[1] * distinv *
  139.             maxscreenscaleinv * (fieldofview / 2.0);
  140.     pavailsurf->zinv00 = plane->normal.v[2] * distinv -
  141.             xcenter * pavailsurf->zinvstepx -
  142.             ycenter * pavailsurf->zinvstepy;
  143.     // Make sure we don't overflow the surface array
  144.     if (pavailsurf < &surfs[MAX_SURFS])
  145.         pavailsurf++;
  146. }
  147. // Scan all the edges in the global edge table into spans.
  148. void ScanEdges (void)
  149. {
  150.     int     x, y;
  151.     double  fx, fy, zinv, zinv2;
  152.     edge_t  *pedge, *pedge2, *ptemp;
  153.     span_t  *pspan;
  154.     surf_t  *psurf, *psurf2;
  155.  
  156.     pspan = spans;
  157.     // Set up the active edge list as initially empty, containing
  158.     // only the sentinels (which are also the background fill). Most
  159.     // of these fields could be set up just once at start-up
  160.     edgehead.pnext = &edgetail;
  161.     edgehead.pprev = NULL;
  162.     edgehead.x = -0xFFFF;           // left edge of screen
  163.     edgehead.leading = 1;
  164.     edgehead.psurf = &surfstack;
  165.     edgetail.pnext = NULL;          // mark edge of list
  166.     edgetail.pprev = &edgehead;
  167.     edgetail.x = DIBWidth << 16;    // right edge of screen
  168.     edgetail.leading = 0;
  169.     edgetail.psurf = &surfstack;
  170.     // Background surface is the entire stack initially, and is infinitely far
  171.     // away, so everything sorts in front of it. Could be set once at start-up
  172.     surfstack.pnext = surfstack.pprev = &surfstack;
  173.     surfstack.color = 0;
  174.     surfstack.zinv00 = -999999.0;
  175.     surfstack.zinvstepx = surfstack.zinvstepy = 0.0;
  176.     for (y=0 ; y<DIBHeight ; y++) {
  177.         fy = (double)y;
  178.         // Sort in any edges that start on this scan
  179.         pedge = newedges[y].pnext;
  180.         pedge2 = &edgehead;
  181.         while (pedge != &maxedge) {
  182.             while (pedge->x > pedge2->pnext->x)
  183.                 pedge2 = pedge2->pnext;
  184.             ptemp = pedge->pnext;
  185.             pedge->pnext = pedge2->pnext;
  186.             pedge->pprev = pedge2;
  187.             pedge2->pnext->pprev = pedge;
  188.             pedge2->pnext = pedge;
  189.             pedge2 = pedge;
  190.             pedge = ptemp;
  191.         }
  192.         // Scan out the active edges into spans. Start out with left background
  193.         // edge already inserted, and surface stack containing only background
  194.         surfstack.state = 1;
  195.         surfstack.visxstart = 0;
  196.         for (pedge=edgehead.pnext ; pedge ; pedge=pedge->pnext) {
  197.             psurf = pedge->psurf;
  198.             if (pedge->leading) {
  199.                 // It's a leading edge. Figure out where it is relative to the
  200.